package code.starivan.leetcode;

import code.starivan.niuke.others.MaxDivision;

/**
 * Created by Ivan on 2015/10/23.
 */

/*
Find the contiguous subarray within an array (containing at least one number) which has the largest product.

        For example, given the array [2,3,-2,4],
        the contiguous subarray [2,3] has the largest product = 6.
*/

public class N152_MaximumProductSubarray {
    public static void test(){
        int[] nums=new int[]{-2,3,-4};
        System.out.println(new N152_MaximumProductSubarray().maxProduct(nums));
    }


    public int maxProduct(int[] nums) {
        if(nums==null||nums.length==0){
            return 0;
        }

        int max=nums[0];
        int min=nums[0];
        int maxProduct=nums[0];
        for(int i=1;i<nums.length;++i){
            int tmpMax=max*nums[i];
            int tmpMin=min*nums[i];
            max= Math.max(Math.max(tmpMax,tmpMin),nums[i]);
            min= Math.min(Math.min(tmpMax, tmpMin), nums[i]);
            maxProduct=Math.max(maxProduct,max);
        }

        return maxProduct;
    }
}
